package com.xzc.datastruc.ujava.c05;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import org.junit.Test;

/**
 * 最大临近子序列和问题-194
 *
 * @author xzc
 */
public class C05_1_MaxSubseqSum {
    static int seqStart = 0;
    static int seqEnd = 0;

    /*
     * N^3 10000个元素寻找就玩完了。
     */
    public static int fun_3(int[] a) {
        int maxSum = 0;

        for (int i = 0; i < a.length; i++) {
            for (int j = i; j < a.length; j++) {
                int thisSum = 0;
                for (int k = i; k <= j; k++) {
                    thisSum += a[k];
                }
                if (thisSum > maxSum) {
                    maxSum = thisSum;
                    seqStart = i;
                    seqEnd = j;
                }
            }
        }

        return maxSum;
    }

    /*
     * N^2 n3中thisSum在k中，j-1的和丢失，又要重新算
     */
    public static long fun_2(int[] a) {
        long maxSum = 0;

        for (int i = 0; i < a.length; i++) {
            long thisSum = 0;
            for (int j = i; j < a.length; j++) {
                thisSum += a[j];
                if (thisSum > maxSum) {
                    maxSum = thisSum;
                    seqStart = i;
                    seqEnd = j;
                }
            }
        }

        System.out.println("n2- " + seqStart + " " + seqEnd);
        return maxSum;
    }

    /*
     * N n2 5.3证明如果一个序列的第一个子序列<0，那么这个子序列是可以舍去的，最大子序列肯定不会包含它。
     */
    public static long fun_1(int[] a) {
        long maxSum = 0;
        long thisSum = 0;

        for (int i = 0, j = 0; j < a.length; j++) {
            thisSum += a[j];
            if (thisSum > maxSum) {
                maxSum = thisSum;
                seqStart = i;
                seqEnd = j;
            } else if (thisSum < 0) {
                i = j + 1;
                thisSum = 0;
            }
        }

        System.out.println("n- " + seqStart + " " + seqEnd);
        return maxSum;
    }

    @Test
    public void test() {
        int len = 1000;
        int abc[] = new int[len];
        for (int i = 0; i < len; i++) {
//            abc[i] = new Random().nextInt(20) - 10;
            abc[i] = new Random().nextInt();
            System.out.println(i + " " + abc[i]);
        }
        long bt = System.nanoTime();
//        int maxSum_3 = C05_1_MaxSubseqSum.fun_3(abc);
        long maxSum_2 = C05_1_MaxSubseqSum.fun_2(abc);
        long maxSum_1 = C05_1_MaxSubseqSum.fun_1(abc);
        System.out.println(maxSum_1 + " " + maxSum_2);
        System.out.println(System.nanoTime() - bt);
    }

}
